﻿#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;


//排序+双指针
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ret;
        int n = nums.size();
        for (int a = 0; a < n;) //为什么不是size()-1?
        {
            for (int b = a + 1; b < n;)
            {
                int left = b + 1;
                long long aim = (long long)target - nums[a] - nums[b];//int 数据范围不够
                int right = n - 1;
                while (left < right)
                {
                    
                    int sum = nums[left] + nums[right];
                    
                    if (sum > aim)
                    {
                        right--;
                    }
                    else if (sum < aim)
                    {
                        left++;
                    }
                    else
                    {
                        ret.push_back({ nums[a],nums[b], nums[left], nums[right] });
                        /*ret.push_back(vector<int>({ a, left, right }));*/
                        right--;
                        left++;
                        //左右指针去重
                        while (nums[left] == nums[left - 1] && left < right)//这里为什么不用If
                        {
                            left++;
                        }
                        while (nums[right] == nums[right + 1] && right > left)  //防止越界
                        {
                            right--;
                        }
                    }
                }
                //b去重
                b++;
                //注意b < n一定要放在nums[b] == nums[b - 1]之前
                while (b < n && nums[b] == nums[b - 1] )  //防止越界  
                {
                    b++;
                }
            }
            //a去重
            a++;
            //注意a < n一定要放在nums[a] == nums[a - 1]之前
            while (a < n && nums[a] == nums[a - 1] )  //防止越界
            {
                a++;
            }
        }
        return ret;
    }
};



int main()
{
    vector<int> a = { 0 };
    vector<int>& b = a;
    vector<vector<int>> c = Solution().fourSum(b, 0);

    return 0;
}


//
//
//class Solution
//{
//public:
//    vector<vector<int>> fourSum(vector<int>& nums, int target)
//    {
//        vector<vector<int>> ret;
//        // 1. 排序
//        sort(nums.begin(), nums.end());
//        // 2. 利⽤双指针解决问题
//        int n = nums.size();
//        for (int i = 0; i < n; ) // 固定数 a
//        {
//            // 利⽤ 三数之和
//            for (int j = i + 1; j < n; ) // 固定数 b
//            {
//                // 双指针
//                int left = j + 1, right = n - 1;
//                long long aim = (long long)target - nums[i] - nums[j];
//                while (left < right)
//                {
//                    int sum = nums[left] + nums[right];
//                    if (sum < aim) left++;
//                    else if (sum > aim) right--;
//                    else
//                    {
//                        ret.push_back({ nums[i], nums[j], nums[left++],
//                       nums[right--] });
//                        // 去重⼀
//                        while (left < right && nums[left] == nums[left - 1])
//                            left++;
//                        while (left < right && nums[right] == nums[right + 1])
//                            right--;
//                    }
//                }
//                // 去重⼆
//                j++;
//                while (j < n && nums[j] == nums[j - 1]) j++;
//            }
//            // 去重三
//            i++;
//            while (i < n && nums[i] == nums[i - 1]) i++;
//        }
//        return ret;
//    }
//};